package com.gitee.feizns.explore.data_structure.union_find;

import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeSet;

/**
 * 721. 账户合并
 * @author feizns
 * @since 2020/3/12
 */
public class AccountsMerge {

    //[
    // ["John","johnsmith@mail.com","john_newyork@mail.com"],
    // ["John","johnsmith@mail.com","john00@mail.com"],
    // ["Mary","mary@mail.com"],
    // ["John","johnnybravo@mail.com"]
    // ]

    //[
    // ["John","johnnybravo@mail.com"],
    // ["John","johnsmith@mail.com","john00@mail.com","john_newyork@mail.com"],
    // ["Mary","mary@mail.com"]
    // ]
    //预期结果
    //[
    // ["John","john00@mail.com","john_newyork@mail.com","johnsmith@mail.com"],
    // ["Mary","mary@mail.com"],
    // ["John","johnnybravo@mail.com"]
    // ]

    static List<List<String>> ACCOUNTS = Arrays.asList(
            Arrays.asList("John", "johnsmith@mail.com", "john_newyork@mail.com"),
            Arrays.asList("John", "johnsmith@mail.com", "john00@mail.com"),
            Arrays.asList("John", "johnnybravo@mail.com"),
            Arrays.asList("Mary", "mary@mail.com")
    );

    public static void main(String[] args) {
        System.out.println(accountsMerge(ACCOUNTS));
    }

//[
// ["John", "johnsmith@mail.com", "john00@mail.com"],
// ["John", "johnnybravo@mail.com"],
// ["John", "johnsmith@mail.com", "john_newyork@mail.com"],
// ["Mary", "mary@mail.com"]
// ]

//[
// ["John", 'john00@mail.com', 'john_newyork@mail.com', 'johnsmith@mail.com'],
// ["John", "johnnybravo@mail.com"],
// ["Mary", "mary@mail.com"]
// ]

    public static List<List<String>> accountsMerge(List<List<String>> accounts) {
        Map<String, String> emailToName = new HashMap<>();
        Uf uf = new Uf();
        for (List<String> account : accounts) {
            String name = account.get(0);
            for (int i = 1; i < account.size(); i++) {
                String item = account.get(i);
                emailToName.put(item, name);
                uf.add(item);
            }
            for (int i = 1; i < account.size() - 1; i++)
                uf.union(account.get(i), account.get(i + 1));
        }
        List<List<String>> ret = new LinkedList<>();
        Map<String, Set<String>> map = uf.ret();
        for (Map.Entry<String, Set<String>> entry : map.entrySet()) {
            List<String> tmp = new LinkedList<>();
            tmp.add(emailToName.get(entry.getKey()));
            entry.getValue().forEach(tmp::add);
            ret.add(tmp);
        }
        return ret;
    }

    static class Uf {
        Map<String, String> PARENT = new LinkedHashMap<>();
        Set<String> roots = new HashSet<>();
        void add(String q) {
            if ( !PARENT.containsKey(q) ) {
                PARENT.put(q, q);
                roots.add(q);
            }
        }
        void union(String p, String q) {
            String pr = find(p);
            String qr = find(q);
            if ( pr != null && qr != null && !pr.equals(qr) ) {
                PARENT.put(pr, qr);
                roots.remove(pr);
            }
        }
        String find(String q) {
            String s = PARENT.get(q);
            if ( s != null ) {
                if ( !s.equals(q) ) {
                    String s1 = find(s);
                    PARENT.put(q, s1);
                    return s1;
                }
                return s;
            }
            return null;
        }
        Map<String, Set<String>> ret() {
            Map<String, Set<String>> ret = new LinkedHashMap<>();
            for (String s : roots)
                ret.put(s, new TreeSet<>());
            for (String s1 : PARENT.keySet()) {
                ret.get(find(s1)).add(s1);
            }
            return ret;
        }
    }

}
